package q23_mergeKLists;

import CommonClass.Common.ListNode;

import static CommonClass.Common.generateList;
import static CommonClass.Common.printList;

public class Solution_2 {
    public static void main(String[] args) {
        ListNode a = generateList(new int[]{1,2,3});
        ListNode b = generateList(new int[]{2,3,4});
        ListNode c = generateList(new int[]{17,22,73});

        printList(mergeKLists(new ListNode[]{a,b,c}));
    }


    public static ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length - 1);

    }



    private static ListNode merge(ListNode[] lists, int l, int r) {
        if(l == r){
            return lists[r];
        }

        if(l > r){
            return null;
        }
        // 数组的中间index
        int mid = (l + r) >> 1;// 这个>>代表算数右移运算符，等价于(l + r) / 2
        return mergeTwoLists(merge(lists,l,mid),merge(lists,mid + 1,r));
    }

    /**
     * 两个有序链表的合并方法
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null || list2 == null) {
            return list1 == null?list2:list1;
        }

        ListNode res = new ListNode(0);
        ListNode head = res;
        while ((list1 != null) && (list2 != null)) {

            if(list1.val > list2.val){
                res.next = new ListNode(list2.val);
                list2 = list2.next;
            }else {
                res.next = new ListNode(list1.val);
                list1 = list1.next;
            }
            res = res.next;
        }
        res.next = (list1 == null)?list2:list1;
        return head.next;
    }

}
